T[ ] 変換について

ウィキペディア小見出し辞書

T[ ] 変換について

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/10 14:50 UTC 版)

「コンビネータ論理」の記事における「T[ ] 変換について」の解説

Tは抽象を消去することが動機となっている。規則3、4は自明である:λx.xは明らかにIと等しく、λx.Eはxが自由変数としてEに出現しない時明らかに(KT[E])である。最初の二つの規則も単純である。変数はそれ自身に変換され、コンビネータ項において許されている適用は単にアプリカンドとコンビネータへの引数の変換である。5番目と6番目の規則は興味深い。5番目は複雑な抽象をコンビネータに変換することを単純に示している。まず本体をコンビネータに変換し、それから抽象を除去する。6番目は実際に抽象を除去する。λx.(E₁ E₂)はaという引数を取り、ラムダ項(E₁ E₂)のxを置き換えて (E₁ E₂)[x : = a]を生成する関数である。しかし、(E₁ E₂)の中のxをaで置き換えるのはちょうどE₁ and E₂を置き換えるのと同じである。だから (E₁ E₂)[x := a] = (E₁[x := a] E₂[x := a]) (λx.(E₁ E₂) a) = ((λx.E₁ a) (λx.E₂ a)) = (S λx.E₁ λx.E₂ a) = ((S λx.E₁ λx.E₂) a) 外延的同値性によって、 λx.(E₁ E2) = (S λx.E₁ λx.E₂) したがって、λx.(E₁ E₂)と等しいコンビネータを見つけるには、(S λx.E₁ λx.E₂)と等しいコンビネータを探せば十分である。そして (S T[λx.E₁] T[λx.E₂]) は明らかにその要件に適合する。E₁とE₂がそれぞれ(E₁ E₂)より厳密に少ない適用を含むため、再帰はすべての変数及びλx.Eの形の項において終了させなければならない。